// https://leetcode.cn/problems/longest-arithmetic-subsequence/description/

// 算法思路总结：
// 1. 使用动态规划寻找最长等差数列
// 2. dp[i][j]表示以nums[i]、nums[j]结尾的等差序列长度
// 3. 通过2*b-c计算前驱元素，利用哈希表快速查找
// 4. 时间复杂度：O(n²)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution 
{
public:
    int longestArithSeqLength(vector<int>& nums) 
    {
        int m = nums.size();
        if (m <= 2) return m;

        vector<vector<int>> dp(m, vector<int>(m, 2));
        unordered_map<int, int> up;
        int ret = 2;

        for (int i = 0; i < m - 1; i++) 
        {
            for (int j = i + 1; j < m; j++) 
            {
                int b = nums[i], c = nums[j];
                int a = 2 * b - c;
                if (up.count(a)) 
                {
                    dp[i][j] = dp[up[a]][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
            up[nums[i]] = i;
        }
        return ret;
    }
};


int main()
{
    vector<int> v1 = {3,6,9,12}, v2 = {9,4,7,2,10};
    Solution sol;

    cout << sol.longestArithSeqLength(v1) << endl;
    cout << sol.longestArithSeqLength(v2) << endl;

    return 0;
}